typedef struct ListNode
{
    int val;
    ListNode* prev;
    ListNode* next;

    ListNode(int _val = 0, ListNode* _prev = nullptr, ListNode* _next = nullptr)
        : val(_val), prev(_prev),next(_next)
    {
    }
}*Node,ListNode;

//链表中的常见操作：1.new一个新节点  2.头插节点   3.尾插节点
int main()
{
    Node headnode = new ListNode();//定义一个哨兵位头节点作为链表的头节点容易判断临界条件
    Node head=headnode;
    // ListNode node1(2);
    // head->next=&node1;
    head->next = new ListNode(2);
    head=head->next;
    head->next = new ListNode(3);
    head = head->next;
    
    //删除new的节点
    while(headnode)
    {
        Node tmp = headnode->next;
        delete headnode;
        headnode = tmp;
    }
    return 0;
}



//1.合并k个升序链表
class Solution {
public:
    //仿函数
    class Compare
    {
        public:
        bool operator()(const ListNode* node_1,const ListNode* node_2)
        {
            return node_1->val > node_2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(0 == lists.size())
        return nullptr;
        int size = lists.size();
        priority_queue<ListNode*,vector<ListNode*>,Compare> q;
        for(int i = 0;i<size;++i)
        {
            if(lists[i] != nullptr)
            q.push(lists[i]);
        }
        ListNode* head = new ListNode();
        ListNode* cur = head;
        while(!q.empty())
        {
            ListNode* tmp = q.top();
            q.pop();
            cur->next = tmp;
            cur = cur->next;
            if(tmp->next != nullptr)
            q.push(tmp->next);
        }
        cur = head->next;
        delete head;
        return cur;
    }
};

//回文链表

//解法一：栈+快慢指针
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        //空间复杂度O(n)
        int size = 0;
        ListNode* cur = head;
        while(cur)
        {
            size++;
            cur = cur->next;
        }
        if(1 == size)
        return true;
        //找中间节点的前一个节点
        cur = head;
        int cnt = 0;
        while(cnt < (size/2 -1))
        {
            cnt++;
            cur = cur->next;
        }
        //细节处理
        ListNode* tmp = nullptr;
        if(size%2 == 0)
        tmp = cur->next;
        else
        tmp = cur->next->next;
        cur->next = nullptr;
        //将链表中间节点后的节点入栈
        stack<ListNode*,vector<ListNode*>> mystack;
        while(tmp)
        {
            mystack.push(tmp);
            tmp = tmp->next;
        }
        while(head || !mystack.empty())
        {
            ListNode* node = mystack.top();
            if(head->val != node->val)
            return false;
            head = head->next;
            mystack.pop();
        }
        return true;
    }
};

//解法二：快慢指针+反转链表
class Solution {
public:
    ListNode* ReverseList(ListNode* tmp)
    {
        ListNode* prev = nullptr,*next = nullptr;
        while(tmp)
        {
            next = tmp->next;
            tmp->next = prev;
            prev = tmp;
            tmp = next;
        }
        return prev;
    }
    bool isPalindrome(ListNode* head) {
        
        //空间复杂度是O(1)
        ListNode* cur = head;
        int size = 0;
        while(cur)
        {
            ++size;
            cur = cur->next;
        }
        if(1 == size)
        return true;

        int cnt = 0;
        cur = head;
        while(cnt < (size/2 - 1)) //这里比较重要，目的是找到链表中点的前一个位置
        {
            ++cnt;
            cur = cur->next;
        }
        ListNode* tmp = nullptr;
        if(size % 2 == 0) //为偶数的时候
        {
            tmp = cur->next;
            cur->next = nullptr;
            //翻转后半部分链表
            //ListNode* new_head = new ListNode(0,tmp);
            ListNode* prev = ReverseList(tmp);
            while(head || prev)
            {
                if(head->val != prev->val)
                return false;
                head = head->next;
                prev = prev->next;
            }
            return true;
        }
        else
        {
            tmp = cur->next->next;
            cur->next = nullptr;
            ListNode* prev = ReverseList(tmp);
            while(head || prev)
            {
                if(head->val != prev->val)
                return false;
                head = head->next;
                prev = prev->next;
            }
            return true;
        }
    }
};